package cn.anquing.datastructure.search;

import cn.anquing.datastructure.sort.ISort;

import java.util.Comparator;

/**
 * 折半查找（二分查找、二分搜索）
 * 需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式，因为加法运算可能导致整数越界，这里应该使用以下三种方式之一：low + (high - low) / 2或low + (high – low) >> 1或(low + high) >>> 1（>>>是逻辑右移，是不带符号位的右移）
 * @author wangquanqing
 * @since 2021/3/24 16:00
 */
public class BinarySearch {

    /**
     * 使用循环.
     *
     * <p>search.
     *
     * @author wangquanqing
     * @since 2021/3/24 16:04
     * @param list 有序数组
     * @param comparator  比较规则
     * @param key 搜索对象
     * @return void
     */
    public static  <T> int search(T[] list, Comparator<T> comparator,T key){

        int low = 0;
        int high = list.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if (comparator.compare(key, list[mid]) > 0) {
                low = mid + 1;
            }else if (comparator.compare(key, list[mid]) < 0) {
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 使用递归.
     *
     * <p>search.
     *
     * @author wangquanqing
     * @since 2021/3/24 17:17
     * @param list 有序数组
     * @param comparator 比较规则
     * @param key 搜索对象
     * @param low 最小下标
     * @param high 最大下标
     * @return int
     */
    public static <T> int search(T[] list, Comparator<T> comparator,T key,int low ,int high){

        if (low <= high){
            int mid = low + ((high - low) >> 1);
            if (comparator.compare(key, list[mid]) > 0) {
                low = mid + 1;
                return search(list, comparator, key, low, high);
            }else if (comparator.compare(key, list[mid]) < 0) {
                high = mid - 1;
                return search(list, comparator, key, low, high);
            }else {
                return mid;
            }
        }else{
            return -1;
        }

    }


}
